package zcw.com.lib_leet_code;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by 朱城委 on 2022/2/22.<br><br>
 *
 * 中等：和为 K 的子数组
 */
public class Topic560 {
    public static void main(String[] args) {
        BaseSolution solution = new Solution2();

        int[] array = new int[] {1, 1, 1};
        System.out.println(solution.subarraySum(array, 2));

        array = new int[] {1, 2, 3};
        System.out.println(solution.subarraySum(array, 3));
    }

    private interface BaseSolution {
        int subarraySum(int[] nums, int k);
    }

    private static class Solution1 implements BaseSolution {

        @Override
        public int subarraySum(int[] nums, int k) {
            int counter = 0;

            for(int i = 0; i < nums.length; i++) {
                int sum = 0;
                for(int end = i; end >= 0; end--) {
                    sum += nums[end];
                    if(sum == k) {
                        counter++;
                    }
                }
            }

            return counter;
        }
    }

    private static class Solution2 implements BaseSolution {

        @Override
        public int subarraySum(int[] nums, int k) {
            int counter = 0; int sum = 0;
            Map<Integer, Integer> map = new HashMap<>();
            map.put(0, 1);

            for (int num : nums) {
                sum += num;
                if (map.containsKey(sum - k)) {
                    counter += map.get(sum - k);
                }

                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }

            return counter;
        }
    }
}
